<head>
    <meta charset="UTF-8">
<title>算法训练 The Traveling Judges Problem</title>
<link rel="stylesheet" href="../css/main.css">
</head>
 <div>【问题描述】</div>
<div>一组人要担任在一个特定城市举办的比赛的评委，他们需要找到最便宜的租车方式使得每个人都到达目标城市。他们观察发现，如果几个人在旅途的某一段坐同一辆租的车，就可以减少总费用。你的任务就是找出这些人应该采取的路线使得租车的总费用最小。</div>
<div>我们假定：</div>
<div>1. 租一辆车的费用与它行驶的距离成正比，没有燃油、保险、乘客人数多于一个等产生的额外费用。</div>
<div>2. 所有车的费用与行驶距离的比例相同。</div>
<div>3. 一辆车可以容纳任意数量的乘客。</div>
<div>4. 任意一对城市之间最多只有一条道路直接相连，每条道路都是双向的且长度大于0。</div>
<div>5. 每个人的起始城市到目标城市都至少有一种路线。</div>
<div>6. 若多个人的路线中经过同一城市，则这些人从该城市到目标城市必乘同一辆车。</div>
<div>7. 一个人可以乘一辆车到某个城市，再乘另一辆车离开该城市。</div>
<div>【输入格式】</div>
<div>第一行包含三个整数nc, dc和nr，表示地图上的城市个数，目标城市的编号和地图上的道路条数。</div>
<div>接下来nr行每行包含三个整数c1, c2和dist，表示一条长度为dist的双向道路(c1, c2)。</div>
<div>接下来一行包含一个整数nj，表示人数。</div>
<div>接下来一行包含nj个整数，表示每个人的起始城市。</div>
<div>【输出格式】</div>
<div>第一行包含&ldquo;distance = &rdquo;和一个整数，表示所租的车行驶的最小总距离。</div>
<div>接下来nj行每行包含一个人的访问路线，城市按访问顺序给出并用&ldquo;-&rdquo;连接。</div>
<div>存在多种方案时，选择需要访问到的城市集合元素最少的一种；仍然存在多种方案时，选择集合元素升序排列后字典序最小的一种。</div>
<div>【样例输入】</div>
<div>5 3 5</div>
<div>1 2 1</div>
<div>2 3 2</div>
<div>3 4 3</div>
<div>4 5 1</div>
<div>2 4 2</div>
<div>2</div>
<div>5 1</div>
<div>【样例输出】</div>
<div>distance = 6</div>
<div>5-4-2-3</div>
<div>1-2-3</div>
<div>【样例输入】</div>
<div>4 4 3</div>
<div>1 3 1</div>
<div>2 3 2</div>
<div>3 4 2</div>
<div>2</div>
<div>1 2</div>
<div>【样例输出】</div>
<div>distance = 5</div>
<div>1-3-4</div>
<div>2-3-4</div>
<div>【样例输入】</div>
<div>3 3 3</div>
<div>1 2 2</div>
<div>1 3 3</div>
<div>2 3 1</div>
<div>2</div>
<div>2 1</div>
<div>【样例输出】</div>
<div>distance = 3</div>
<div>2-3</div>
<div>1-2-3</div>
<div>【数据规模和约定】</div>
<div>对于30%的数据，1 &lt;= nc &lt;= 8。</div>
<div>对于100%的数据，1 &lt;= nc &lt;= 20，1 &lt;= nj &lt;= 10，1 &lt;= dist &lt;= 100。</div>